/*
 * =====================================================================================
 *
 *       Filename:  4.cpp
 *
 *    Description:  编程珠玑 第四章
 *
 *        Version:  1.0
 *        Created:  2011-11-15 9:27:31
 *       Revision:  none
 *       Compiler:  gcc
 *
 *         Author:  YOUR NAME (),
 *        Company:
 *
 * =====================================================================================
 */

#include <iostream>
#include "UserTime.h"

void bubble_sort(int array[], int l, int r)
{
    for (int j = r; j > l; --j) {
        for (int i = l; i < j; ++i) {
            if (array[i] > array[i + 1]) {
                std::swap(array[i], array[i + 1]);
            }
        }
    }
}

int linear_search(int array[], int n, int v)
{
    for (int i = 0; i < n; ++i) {
        if (v == array[i]) {
            return i;
        }
    }

    return -1;
}

int search_and_comp(int array[], int n, int v, int &cnt_comp)
{
    int left, right, middle;

    left = 0, right = n - 1;

    while (left <= right) {
        middle = left + (right - left) / 2;

        if (array[middle] > v) {
            right = middle - 1;
            cnt_comp++;
        } else if (array[middle] < v) {
            left = middle + 1;
            cnt_comp++;
        } else {
            cnt_comp++;
            return middle;
        }
    }

    return -1;
}

int main(int argc, char *argv[])
{
    srand(unsigned(time(NULL)));


    for (int i = 1; i <= 10000000; i *= 10) {
        int cnt = 10 * i;
        int *array = new int[cnt];

        for (int k = 0; k < cnt; ++k) {
            array[k] = k;
        }

        CUserTime timer;
        int count_comp = 0;
        int val = rand() % cnt;
        search_and_comp(array, cnt, val, count_comp);
        std::cout << "the binary search running time of " << cnt << " counts is " << timer.lapse()
                  << " and the comp count is " << count_comp << std::endl;

        timer.start();
        linear_search(array, cnt, val);
        std::cout << "the linear search running time of " << cnt << " counts is " << timer.lapse() << std::endl;

        delete [] array;
    }

    for (int i = 1; i <= 10; ++i) {
        const int cnt = 10000*i;
        int *array = new int[cnt];

        for (int k = 0; k < cnt; ++k) {
            array[k] = rand()%cnt;
        }

        CUserTime timer;
        bubble_sort(array, 0, cnt - 1);
        std::cout << "the bubble sort running time of " << cnt << " counts is " << timer.lapse() << std::endl;
        delete [] array;
    }

    return 0;
}
